#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    namespace impl
    {
        /**
         * @brief   返回指定下标的元素的左子结点下标
         * @param   idx     元素下标
         * @return  元素左子结点下标
         */
        std::size_t leftChild(std::size_t idx)
        {
            return 2 * idx + 1;
        }

        /**
         * @brief   返回堆的最后一个非叶结点的下标
         * @param   n   堆数组的长度
         * @returns 堆的最后一个非叶结点的下标
         */
        std::size_t lastNotLeaf(std::size_t n)
        {
            return n / 2 - 1;
        }

        /**
         * @brief   堆的向下调整函数
         * @tparam  T       基本数据类型
         * @param   vec     堆数组
         * @param   left    数组左边界
         * @param   right   数组右边界
         */
        template <typename T>
        void heapAdjust(std::vector<T> &vec, std::size_t left, std::size_t right)
        {
            const T tmp = vec[left];
            std::size_t i = leftChild(left);

            while (i <= right)
            {
                while (i < right && vec[i] < vec[i + 1])
                {
                    // 比较左右子结点，选较大的数的下标存入 i
                    i++;
                }
                if (tmp > vec[i])
                {
                    // 调整节点的数字已经大于子结点，说明调整完毕
                    break;
                }

                vec[left] = vec[i];
                left = i;
                i = leftChild(i);
            }

            vec[left] = tmp;
        }
    } // namespace impl

    /**
     * @brief   堆的向下调整函数
     * @note    堆数组的元素是从下标 0 开始存储的
     * @tparam  T       基本数据类型
     * @param   vec     堆数组
     */
    template <typename T>
    void HeapSort(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        // 建立大根堆
        // ! 这里不能写：for (size_t i = impl::lastNotLeaf(len); i >= 0; --i)
        // ! 因为 size_t 是无符号类型，i 总是不小于 0，这里的条件判断会出问题
        // * 除了下面这种写法外，
        // * for (size_t i = impl::lastNotLeaf(len); i-- >= 0) 也是正确的
        for (int i = static_cast<int>(impl::lastNotLeaf(len)); i >= 0; --i)
        {
            impl::heapAdjust(vec, static_cast<size_t>(i), len - 1);
        }

        // 每次将堆顶和最后一个叶结点交换，并向下调整堆
        for (size_t i = len - 1; i > 0; --i)
        {
            std::swap(vec[i], vec[0]);
            impl::heapAdjust(vec, 0, i - 1);
        }
    }
} // namespace sorting
